A number of applications require the computation of the trace of a matrixthat is implicitly available through a function. A common example of a functionis the inverse of a large, sparse matrix, which is the focus of this paper.When the evaluation of the function is expensive, the task is computationallychallenging because the standard approach is based on a Monte Carlo methodwhich converges slowly. We present a different approach that exploits thepattern correlation, if present, between the diagonal of the inverse of thematrix and the diagonal of some approximate inverse that can be computedinexpensively. We leverage various sampling and fitting techniques to fit thediagonal of the approximation to the diagonal of the inverse. Depending on thequality of the approximate inverse, our method may serve as a standalone kernelfor providing a fast trace estimate with a small number of samples.Furthermore, the method can be used as a variance reduction method for MonteCarlo in some cases. This is decided dynamically by our algorithm. An extensiveset of experiments with various technique combinations on several matrices fromsome real applications demonstrate the potential of our method.
展开▼
